package com.hanxiaozhang.no10leetcode.link;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * 给一个链表，返回链表中环的起始位置（连接点），如果没有环则返回空。
 * 注意不要修改原链表，且使用常量存储空间。
 * <p>
 * 参考：com.hanxiaozhang.link.fastslowpointer.FastSlowPointerTopic#getConnectNode(com.hanxiaozhang.link.singlylink.Node)
 * <p>
 * 概念：
 * 1. 碰撞点：快慢指针有环时，相遇的点。
 * 2. 定理：碰撞点到连接点的距离 = 头指针到连接点的距离。
 * <p>
 * 思路：
 * 第一轮快慢指针，找到碰撞点。
 * 第二轮从头指针和碰撞点开始走（每次走一步），再相遇的那个点就是连接点。
 *
 * @author hanxinghua
 * @create 2024/2/2
 * @since 1.0.0
 */
public class No142LinkedListCycleII {

    public static void main(String[] args) {

        // 1->2->3 <- 8 <- 7
        //        \->       \ ->
        //         4        6
        //          \->   / ->
        //             5
        Node head1 = new Node(1);
        head1.next = new Node(2);
        Node node3 = new Node(3);
        head1.next.next = node3;
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(6);
        head1.next.next.next.next.next.next = new Node(7);
        head1.next.next.next.next.next.next.next = new Node(8);
        head1.next.next.next.next.next.next.next.next = node3;

        System.out.println(getConnectNode(head1));
    }


    /**
     * 获取连接点
     * <p>
     * 定理：碰撞点到连接点的距离 = 头指针到连接点的距离。
     * 因此，分别从头指针和碰撞点开始走，再相遇的那个点就是连接点。
     *
     * @param head
     * @return
     */
    private static Node<Integer> getConnectNode(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }

        Node slow = head.next;
        Node fast = head.next.next;
        boolean flag = false;
        while (fast.next != null && fast.next.next != null) {
            if (slow == fast) {
                flag = true;
                break;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        if (!flag) {
            return null;
        }
        // 分别从头指针和碰撞点开始走，再相遇的那个点就是连接点。
        while (true) {
            if (head == slow) {
                return slow;
            }
            head = head.next;
            slow = slow.next;
        }
    }

}
